#pragma once

/**
 * 插入算法的实现.
 * 
 * 在已经排好序列的数据中找到合适的位置。
 */
#include <functional>

template<typename T, typename compare = std::less<T>>
void Insertion(T* pElems, size_t len){
    if(pElems == nullptr)
        return;

    if(len < 1)
        return;

    compare comp;
    for(int i = 1; i < len; ++i){
        T elem = pElems[i]; //将需要比较的元素A拿出来
        
        int preIndex = i - 1;

        while(preIndex >= 0 && comp(elem, pElems[preIndex])){ //比较前一个元素谁符合
            pElems[preIndex + 1] = pElems[preIndex]; //比较后，使得前一个向后移动(这个时候需要注意的是元素A已经被单独拿出了，所以会空出一个位置来。)
            --preIndex; //向前移动
        }

        pElems[preIndex + 1] = elem; //空出的位置就是需要放入元素A的位置。
    }
}

template<typename T, typename compare = std::less<T>>
void InsertionTrace(T* pElems, size_t offset){
    compare comp;
    T elem = pElems[offset];
    int preIndex = offset - 1;

    while(preIndex >= 0 && comp(elem, pElems[preIndex])){ //比较前一个元素谁符合
        pElems[preIndex + 1] = pElems[preIndex]; //比较后，使得前一个向后移动(这个时候需要注意的是元素A已经被单独拿出了，所以会空出一个位置来。)
        --preIndex; //向前移动
    }

    pElems[preIndex + 1] = elem;
}

template<typename T, typename compare = std::less<T>>
void InsertionRecursion(T* pElems, size_t lastIndex, size_t offset = 1){
    if(pElems == nullptr)
        return;

    InsertionTrace<T, compare>(pElems, offset);

    if(offset < lastIndex){
        InsertionRecursion<T, compare>(pElems, lastIndex, offset + 1);
    }
}

